package leetcode.code0943;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution4 implements IDebug {

	int MAX = 300;

	public String shortestSuperstring(String[] words) {
		int len = words.length;
//		int[][] adds = new int[len][len];
		String[][] add = new String[len][len];
		for (int i = 0; i < len; i++) {
			String s1 = words[i];
			for (int j = 0; j < len; j++) {
				if (j != i) {
					String s2 = words[j];
//					adds[i][j] = s1.length() + s2.length();
					add[i][j] = s1 + s2;
					for (int k = 0; k < s1.length(); k++) {
						if (s2.startsWith(s1.substring(k))) {
//							adds[i][j] = s2.length() - s1.length() + k;
							add[i][j] = s2.substring(s1.length() - k);
							break;
						}
					}
				}
//				else {
//					adds[i][j] = MAX;
//				}
			}
		}
//		H.print(adds);
		H.print(add);
//		int[][] dp = new int[1 << len][len];
		String[][] dps = new String[1 << len][len];
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
//				dp[1 << i][j] = i == j ? words[i].length() : MAX;
				if (i == j) {
					dps[1 << i][j] = words[i];
				}
			}
		}
		for (int i = 1; i < 1 << len; i++) {
			for (int j = 0; j < len; j++) {
				if (Integer.bitCount(i) == 1) {
					continue;
				}
				int p = 1 << j;
				if ((i & p) != 0) {
					int rest = i ^ p;
//					int cur = MAX;
					String curStr = null;
					for (int k = 0; k < len; k++) {
//						cur = Math.min(cur, dp[rest][k] + adds[k][j]);
						if (dps[rest][k] != null && add[k][j] != null) {
							if(curStr == null) {
								curStr = dps[rest][k] + add[k][j]; 
							}else if(curStr.length() > (dps[rest][k] + add[k][j]).length()) {
								curStr = dps[rest][k] + add[k][j]; 
							}
						}
					}
//					dp[i][j] = cur;
					dps[i][j] = curStr;
				} 
//				else {
//					dp[i][j] = MAX;
//				}
			}
		}
//		H.print(dp);
		H.print(dps);
//		int ans = MAX;
//		for (int i = 0; i < len; i++) {
//			ans = Math.min(dp[(1 << len) - 1][i], ans);
//		}
		String ansStr = dps[(1 << len) - 1][0];
		for (int i = 1; i < len; i++) {
			ansStr = dps[(1 << len) - 1][i].length() < ansStr.length()? dps[(1 << len) - 1][i] : ansStr;
		}
//		System.out.println(ans);
		return ansStr;
	}

	@Override
	public void debug4() {
		H.compare("gctaagttcatgcatc",
				this.shortestSuperstring(H.str2array2("[\"catg\",\"ctaagt\",\"gcta\",\"ttca\",\"atgcatc\"]")));
		H.compare("ab", this.shortestSuperstring(H.str2array2("[\"ab\",\"a\",\"b\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		for (int i = 0; i < 100; i++) {
//			System.out.println(Integer.toBinaryString(i));
//		}
	}

}
